package com.lhcai.lc.other;

/**
 * @author lhcstart
 * @create 2023-02-26 16:05
 */

import java.util.*;

/**
 * 查找和最小的 K 对数字
 * 给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
 * 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
 * 请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。
 */
public class lc373 {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

        //大根堆:大的在前，小的在后
        Queue<List<Integer>> pri = new PriorityQueue<>(
                (a, b) -> {
                    return (b.get(0) + b.get(1)) - (a.get(0) + a.get(1));
                }
        );

        int len1 = nums1.length;
        int len2 = nums2.length;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                List<Integer> list = new ArrayList<>();
                int sum = nums1[i] + nums2[j];
                list.add(nums1[i]);
                list.add(nums2[j]);
                if (pri.size() < k) {
                    pri.add(list);
                } else {
                    int s = pri.peek().get(0) + pri.peek().get(1);
                    if (s > sum) {
                        pri.poll();
                        pri.add(list);
                    }else {
                        break;
                    }
                }
            }
        }
        List<List<Integer>> ans = new ArrayList<>(pri);
        return ans;
    }

}
